//
// Created by daiyizheng on 2022/4/12.
//
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
//子数组和子序列类似，子数组属于子序列，子序列可以不连续
class Solution {
public:
    // 动态规划(一)
    int longestPalindromeSubseq(string s) {
        if (s.length()==0)return 0;

        int m = s.length();
        //状态dp[i][j] 表示在区间[i...j] 中最长回文子序列的长度

        vector<vector<int>> dp(m, vector<int>(m,0));

        //初始化，对角线为1， 一个字符的最长回文子序列长度是 1
        for (int i = 0; i < s.length(); ++i) {
            dp[i][i] = 1;
        }
        //状态转移
        // s[i] == s[j]的话，那么 dp[i][j]=2+dp[i+1][j-1]
        //s[i] != s[j]的话， 那么 dp[i][j] = max(dp[i+1][j], dp[i][j-1])

        for (int i = m - 2; i >= 0; i--) {
            for (int j = i + 1; j < m; j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = 2 + dp[i + 1][j - 1];
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][m - 1];
    }
};